/*                  A
 *              B         C
 *                D     E      
 *              F     G   H
 *
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *lchild;
    struct TreeNode *rchild;
} TreeNode;

typedef struct QueueNode {
    struct TreeNode *data;
    struct QueueNode *pre;
    struct QueueNode *next;
} QueueNode;

QueueNode *initQueue()
{
    QueueNode *Q = (QueueNode *)malloc(sizeof(QueueNode));
    Q->data = NULL;
    Q->pre = Q;
    Q->next = Q;
    return Q;
}

int isEmpty(QueueNode *Q) 
{
    if (Q->next == Q) return 1;
    return 0;
}
//保留头节点
void enQueue(QueueNode *Q, TreeNode *data)
{
    QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode));
    node->data = data;
    node->pre = Q->pre; 
    node->next = Q;
    Q->pre->next = node;
    Q->pre = node;
}

TreeNode *deQueue(QueueNode *Q) 
{
    if (isEmpty(Q)) return NULL;
    QueueNode *del = Q->next;
    TreeNode *ret = del->data;
    del->next->pre = Q;
    Q->next = del->next;
    free(del); //感觉这个更好这个防止了内存泄漏
    return ret;
}

void levelTraverse(TreeNode *T, QueueNode *Q)
{ 
    enQueue(Q, T);
    while (!isEmpty(Q)) {
        TreeNode *node = deQueue(Q);
        printf("%c ", node->data); //注意这里要用node->data而不是T->l/rchild
        if (node->lchild) {
            enQueue(Q, node->lchild);
        }
        if (node->rchild) {
            enQueue(Q, node->rchild);
        }
    }
}

void creatTree(TreeNode **T, char *data, int *index)
{
    char ch;
    ch = data[(*index)++];
   
    if (ch == '#') {
        *T = NULL;
    } else {
         *T = (TreeNode*)malloc(sizeof(TreeNode));
        (*T)->data = ch;
        creatTree(&((*T)->lchild), data, index);
        creatTree(&((*T)->rchild), data, index);
    }
}

void preOrder(TreeNode *T) 
{
    if (!T) return ;
    printf("%c ", T->data);
    preOrder(T->lchild);
    preOrder(T->rchild);
}

int main(void) 
{
    QueueNode *Q = initQueue();
    TreeNode *T;
    int index = 0;
    creatTree(&T, "AB#DF###CEG##H###", &index);
    //preOrder(T);
    levelTraverse(T, Q);
    return 0;
}


   